home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-02
/
llist10.zip
/
LLIST.PAS
< prev
next >
Wrap
Pascal/Delphi Source File
|
1990-01-14
|
6KB
|
283 lines
UNIT llist;
{Version 1.0, distributed as LLIST10.ZIP}
{This unit contains objects for doubly-linked lists. See also DEMO.PAS
and TEST.PAS in this archive. For Turbo Pascal 5.5.
Please distribute this unit with its demo and test programs. Also,
please retain in this unit credit to its original author and any
subsequent authors.
Donated to the public domain by Wayne E. Conrad, January, 1990. If you
have any problems or suggestions, please contact me at my BBS:
Pascalaholics Anonymous
(602) 484-9356
2400 bps
The home of WBBS
Lots of source code
}
INTERFACE
{This abstract type is for each node in a list. It contains the data and
methods needed to manage a node on the list, but it does not contain any
useful data. A descendant object should be created which contains the
data you want in each node, as well as any methods to operate upon that
data.}
TYPE
linked_list_ptr = ^linked_list_node;
linked_list_node =
OBJECT
prev: linked_list_ptr;
next: linked_list_ptr;
CONSTRUCTOR init;
DESTRUCTOR done;
PROCEDURE remove;
FUNCTION get_prev: linked_list_ptr;
FUNCTION get_next: linked_list_ptr;
PROCEDURE add_after (VAR node: linked_list_node);
PROCEDURE add_before (VAR node: linked_list_node);
END;
{There must be one of these objects for each linked list.}
TYPE
linked_list_anchor =
OBJECT
first: linked_list_node;
last : linked_list_node;
CONSTRUCTOR init;
DESTRUCTOR done;
PROCEDURE remove_all_nodes;
PROCEDURE destruct_all_nodes;
PROCEDURE dispose_all_nodes;
FUNCTION get_first: linked_list_ptr;
FUNCTION get_last: linked_list_ptr;
FUNCTION empty: Boolean;
PROCEDURE add_to_head (VAR node: linked_list_node);
PROCEDURE add_to_tail (VAR node: linked_list_node);
END;
IMPLEMENTATION
{----- Methods for linked_list_anchor -----}
{Initialize the anchor to an empty list. This method must be called
before the anchor is used.}
CONSTRUCTOR linked_list_anchor.init;
BEGIN
first.init;
last.init;
first.next := @last;
last.prev := @first
END;
{All nodes on the list are removed from the list.}
PROCEDURE linked_list_anchor.remove_all_nodes;
VAR
p : linked_list_ptr;
next: linked_list_ptr;
BEGIN
p := get_first;
WHILE (p <> NIL) DO
BEGIN
next := p^.get_next;
p^.remove;
p := next
END
END;
{All nodes on the list are destructed. All nodes will be removed from
the list, in addition to whatever else the destructor cares to do.}
PROCEDURE linked_list_anchor.destruct_all_nodes;
VAR
p : linked_list_ptr;
next: linked_list_ptr;
BEGIN
p := get_first;
WHILE (p <> NIL) DO
BEGIN
next := p^.get_next;
p^.done;
p := next
END
END;
{All nodes on the list are Disposed. All nodes will be destructed,
removing them from the list, and their memory returned to the heap.}
PROCEDURE linked_list_anchor.dispose_all_nodes;
VAR
p : linked_list_ptr;
next: linked_list_ptr;
BEGIN
p := get_first;
WHILE (p <> NIL) DO
BEGIN
next := p^.get_next;
Dispose (p, done);
p := next
END
END;
{Destruct the anchor. All nodes on the list are removed from the list.
The nodes themselves are not destructed or disposed! If you want to do
THAT, invoke the "destruct_all_nodes" or "dispose_all_nodes" methods.}
DESTRUCTOR linked_list_anchor.done;
VAR
p : linked_list_ptr;
next: linked_list_ptr;
BEGIN
remove_all_nodes
END;
{Returns a pointer to the first node in the list, or NIL if the list is
empty.}
FUNCTION linked_list_anchor.get_first: linked_list_ptr;
BEGIN
IF empty THEN
get_first := NIL
ELSE
get_first := first.next
END;
{Returns a pointer to the last node in the list, or NIL if the list is
empty.}
FUNCTION linked_list_anchor.get_last: linked_list_ptr;
BEGIN
IF empty THEN
get_last := NIL
ELSE
get_last := last.prev
END;
{Returns True if the list is empty.}
FUNCTION linked_list_anchor.empty: Boolean;
BEGIN
empty := first.next = @last
END;
{Add the node to the head of this list. If the node is already on a
list, it is removed from that list first.}
PROCEDURE linked_list_anchor.add_to_head (VAR node: linked_list_node);
BEGIN
node.add_after (first)
END;
{Add the node to the tail of this list. If the node is already on a
list, it is removed from that list first.}
PROCEDURE linked_list_anchor.add_to_tail (VAR node: linked_list_node);
BEGIN
node.add_before (last)
END;
{----- Methods for linked_list_node -----}
{Construct the node. Must be invoked before the node is used.}
CONSTRUCTOR linked_list_node.init;
BEGIN
prev := NIL;
next := NIL
END;
{Destruct the node. If it's on a list, remove it.}
DESTRUCTOR linked_list_node.done;
BEGIN
remove
END;
{If the node is on a list, remove it.}
PROCEDURE linked_list_node.remove;
BEGIN
IF prev <> NIL THEN
prev^.next := next;
IF next <> NIL THEN
next^.prev := prev;
prev := NIL;
next := NIL
END;
{Get the pointer to the previous node, or NIL if there is no previous
node.}
FUNCTION linked_list_node.get_prev: linked_list_ptr;
BEGIN
IF prev^.prev = NIL THEN
get_prev := NIL
ELSE
get_prev := prev
END;
{Get the pointer to the next node, or NIL if there is no next node.}
FUNCTION linked_list_node.get_next: linked_list_ptr;
BEGIN
IF next^.next = NIL THEN
get_next := NIL
ELSE
get_next := next
END;
{If this node is in a list, remove it. Then insert this node into
whatever list p is in, putting it after p.}
PROCEDURE linked_list_node.add_after (VAR node: linked_list_node);
BEGIN
remove;
next := node.next;
prev := @node;
next^.prev := @Self;
prev^.next := @Self
END;
{If this node is in a list, remove it. Then insert this node into
whatever list p is in, putting it before p.}
PROCEDURE linked_list_node.add_before (VAR node: linked_list_node);
BEGIN
remove;
prev := node.prev;
next := @node;
prev^.next := @Self;
next^.prev := @Self
END;
END.